/*
https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/
2616. 最小化数对的最大差值
medium, 方钊堉 2024.09.17
二分查找
*/

class Solution {
public:
    int minimizeMax(vector<int> &nums, int p) {
        // 函数用于在给定的整数数组中，通过配对元素并使这些配对元素差值的最大值最小化。
         // 首先对数组进行排序，这样可以方便我们寻找配对元素。
        sort(nums.begin(), nums.end());
        // 初始化二分查找的左右边界。
        // 左边界初始化为 -1（实际上不会达到此值），右边界为数组中最大值与最小值之差。
        int l = -1;
        int r = nums.back() - nums[0];
        while (l + 1 < r) {
            int ee = l +(r-l)/2;
            int ccc = 0;
            int k=nums.size();
            for (int i = 0; i < k - 1; ++i)
                if (nums[i + 1] - nums[i] <= ee) {
                    ccc+=1;
                    i+=1;
                }
            (ccc >= p ? r : l) = ee;
        }
        // 根据配对的数量调整左右边界。
            // 如果配对的数量大于等于 p，则说明当前假设的最大差值过大，
            // 应该尝试更小的差值，因此更新右边界。
            // 否则，说明差值太小，应该尝试更大的差值，因此更新左边界。
        return r;
    }
};
